The present invention relates to a system and method for facilitating access to and use of geographic data used with a navigation application program that provides navigating features and functions to an end-user, and more particularly, the present invention relates to a geographic database that includes data which represent segments of roads, and in addition includes data which represent aggregations of certain of these segments of roads so that a navigation application program using the geographic database can use either or both of these kinds of data thereby facilitating certain functions and enhancing performance.
Computer-based navigation application programs are available that provide end-users (such as drivers of vehicles in which the navigation systems are installed) with various navigating functions and features. For example, some navigation application programs are able to determine an optimum route to travel by roads between locations. Using input from an end-user, and optionally from equipment that can determine one's physical location (such as a GPS system), a navigation application program can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in a geographic region. The navigation application program may then provide the end-user with information about the optimum route in the form of instructions that identify the maneuvers required to be taken by the end-user to travel from the starting location to the destination location. If the navigation system is located in an automobile, the instructions may take the form of audio instructions that are provided along the way as the end-user is traveling the route. Some navigation application programs are able to show detailed maps on computer displays outlining routes to destinations, the types of maneuvers to be taken at various locations along the routes, locations of certain types of features, and so on.
In order to provide these and other navigating functions, the navigation application program uses one or more detailed databases that include data which represent physical features in a geographic region. The detailed database may include data representing the roads and intersections in a geographic region and also may include information about the roads and intersections in a geographic region, such as turn restrictions at intersections, speed limits along the roads, street names of the various roads, address ranges along the various roads, and so on.
One difficulty in providing geographic data for use by a navigation application program relates to the efficient utilization of the available computer resources of the navigation system on which the navigation application program is run. Computer-based navigation application programs are provided on various platforms including some with relatively limited computer hardware resources. For example, navigation systems may be located in vehicles or may be hand-held. These types of navigation systems typically have relatively limited computer resources, such as limited memory and relatively slow I/O. In order to provide a high a level of functionality in such systems, it is required that the available computer resources be used efficiently.
Given the relatively large size of the geographic database necessary to provide a desired level of navigating functionality to the end-user, it is accepted that all the data records for an entire geographic region cannot be loaded into the memory of the navigation system at the same time. This is especially true for navigation system platforms with limited resources, such as systems installed in vehicles or hand-held systems. Due to the limited memory resources of these navigation systems, it is necessary to load geographic data as needed from a storage medium, such as a CD-ROM disk, into the memory of the navigation system for use by the navigation application program. Unfortunately, as mentioned above, in these types of systems, I/O access from a storage medium may also be relatively slow. Thus, the relatively limited memory resources combined with the relatively slow I/O can limit the performance of some types of navigation systems, resulting in slow response. Aside from being undesirable, slow response in a navigation system may render the system useless for its intended purpose in certain circumstances. For example, if the navigation system is installed in a vehicle, the driver may require information from the navigation system about a desired route in a matter of seconds in order to utilize the information while driving. If the navigation system requires more than several seconds to calculate a route, the driver may have moved beyond the point at which the routing information provided by the navigation system is relevant. Therefore, it is important that navigation systems operate efficiently in order to provide navigating information relatively quickly.
Navigation application programs may also be run on computer platforms that have in general greater memory resources and faster I/O, such as personal computers or networks. Although these systems may have more and faster resources, the considerations related to the efficient use of geographic data still apply, but on a larger scale. With these types of systems, even greater functionality can be provided if the limitations imposed by memory size and I/O are minimized.
Techniques have been devised or implemented to improve navigation system performance by organizing structuring, or arranging the geographic database or the data in the database in particular ways. Because a navigation system uses geographic data in certain known and expected ways to perform known functions, the geographic data can be organized, structured, or arranged in a manner that facilitates their use in these known ways by the navigation system.
One technique that can be implemented in a geographic database to enhance operation of the navigation system is to minimize consideration of minor or secondary roads during calculation of a route. For example, when calculating a route between two locations, it might be inefficient to examine all the possible road segments that diverge from each intersection along a route being calculated, including all secondary streets and alleys. Instead, once a route being calculated is "on" a main road or expressway, it might be preferable to stay on main roads or expressways until it is necessary to exit to secondary roads as the destination is approached. This suppression of minor or secondary roads can be implemented in various ways.
One way to suppress consideration of minor or secondary roads is to use a ranking assigned to roads in a geographic region. The ranking can be related to a functional classification of the roads. Major roads upon which travel is generally faster are assigned a higher ranking and minor roads upon which travel is generally slower are assigned a lower ranking. Using these rankings, data records that represent higher ranked roads can be stored in a manner that eliminates or suppresses intersections with some or all of the lower ranked roads. One way to provide for this suppression is to store the higher ranked roads in one or more separate collections thereby forming separate layers in the geographic database. The higher layers are used when possible. Since the higher layers omit secondary roads, these slower roads are not considered when calculating the route, thereby minimizing the possible road segments to be investigated. This kind of database arrangement may facilitate the route calculation navigation function, thereby providing improved navigation system performance.
If a geographic database is organized in this manner, one difficulty to be addressed is how to make these different layers and/or rankings work together efficiently. Eliminating the lower ranked roads from the higher layers of geographic data may speed up a route calculation function once a calculated route is on the higher ranked road. However by eliminating the data associated with lower ranked roads from higher layers of data, it may be difficult to determine when the higher layers should be used or when the higher ranked roads can be successfully accessed from a lower ranked road.
Accordingly, there continues to be a need for improvements that can provide better navigation system performance. Thus, it is an objective to provide improvements in the storage or use of geographic data that improves performance in a navigation system. Similarly, it is a further objective to develop navigation functions that can exploit the geographic database in improved ways.